Problem statement: zenit13ckk

Tento ročník Zenitu zavŕšime hrou hier - Civilizáciou. Táto hra sa v rôznych verziach teší veľkej popularite už vyše dve desaťročia.

Každá silná civilizácia, ktorá chce vydržať test času, sa musí oprieť o silnú infraštruktúru. V tejto úlohe budeme preto navrhovať čo najefektívnejšie cestné siete, ktoré spoja všetky mestá. Našim cieľom je, aby sa z každého mesta dalo dostať do každého len po políčkach s cestou alebo cez iné mestá (tam je cesta bez toho, aby sme ju stavali).

Nech M označuje mesto, . (bodka) pevninu, O more alebo jazero a X políčko s cestou. Medzi políčkami v mriežke sa dá chodiť aj do šikma. Každé políčko má teda najviac 8 susedov. Mapa korektnej cestnej siete môže vyzerať napríklad takto

...........    ......XXXX.
.....M....M    ...XXM....M
..MXX.X.XX.    ..M........
...OOOOX...    ..XOOOO....
........M..    ...XXXXXM..

Obe cestné siete umožňujú cestovať z každého mesta do každého. Ľavá cestná sieť pozostáva zo šiestich políčok, pravá z dvanástich. Ľavá je optimálna, pretože neexistuje cestná sieť s menej políčkami s cestou (existuje ale viacero rôznych so šiestimi).

Na prvom riadku vstupu sú rozmery mapy R a S, 3 ≤ R,S ≤ 10. Na ďalších R riadkoch je mapa krajiny. Každý riadok pozostáva z S znakov. Tieto znaky sú M, . alebo O (ich význam je rovnaký ako v príklade vyššie).

Na výstup vypíšte jediné číslo: minimálny počet políčok, na ktorých treba postaviť cestu, aby sme dostali cestnú sieť, ktorá spojí všetky mestá v krajine. Samozrejme, nie je možné stavať cestu na vodnej ploche. Môžete predpokladať, že taká cestná sieť existuje. Môžete tiež predpokladať, že mestá sú aspoň dve a že žiadne dve mestá nesusedia (ani len rohom).

Riešenie, ktoré funguje korektne pre krajiny s dvoma mestami môže získať 40% bodov. Ďalších 20% bodov môže získať riešenie fungujúce na mapách s troma mestami. Na zvyšných vstupoch bude najviac 5 miest.

6 10
..OO.....O
...OO..O.M
.MOO..OO..
....M.O..O
OO......OO
OOO..O..MO 

7 

..OO.....O
...OO..O.M
.MOO..OOX.
..X.M.OX.O
OO.X.XXXOO
OOO..O..MO

6 7
MOOOOOM
O.OOO.O
OO.O.OO
OOO.OOO
OOO.OOO
OOOMOOO 

6 

3 6
M...OM
....O.
...... 

5